package binaryTree;

import linkedList.ListNode;
import sun.awt.image.ImageWatched;
import sun.reflect.generics.tree.Tree;

import java.util.*;

public class Question {
    ArrayList<Integer> list = new ArrayList<>();
    /*前序遍历  根左右*/
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null)return null;

        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
    /*中序遍历 左根右*/
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null) return list;
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);
        return list;
    }
    /*后序遍历 左右根*/
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return list;
        inorderTraversal(root.left);
        inorderTraversal(root.right);
        list.add(root.val);
        return list;
    }

    /*迭代遍历*/

    public static void preOrderIteration(TreeNode head) {
        if (head == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(head);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }


    //前序遍历 用一个栈来存储
    public List<Integer> preorderTraversal1(TreeNode root){
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root != null){
            stack.push(root);
        }
        //利用栈的先进后出原则  记录结点  （递归也是这种原理  只不过用了系统栈 不用自己维护一个数据结构）
        while(!stack.isEmpty()){
            TreeNode curNode = stack.pop();
            list.add(curNode.val);
            if (curNode.right != null){
                stack.push(curNode.right);
            }
            if (curNode.left != null){
                stack.push(curNode.left);
            }
        }
        return list;
    }
    /*参考*/
    public static void inOrderIteration(TreeNode head) {
        if (head == null) {
            return;
        }
        TreeNode cur = head;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            if (node.right != null) {
                cur = node.right;
            }
        }
    }

    /*迭代法 中序遍历 左根右*/
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if (root == null)return list;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(!stack.isEmpty() || cur != null){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            //最小左子树 的左叶子结点
            TreeNode minLeftNode = stack.pop();
            list.add(minLeftNode.val);
            //遍历此时的右子树
            if (cur.right != null){
                cur = cur.right;
            }
        }

        return list;
    }
    //迭代 后序遍历二叉树
    public List<Integer> postorderTraversal1(TreeNode root){
        List<Integer> list = new ArrayList<>();
        if (root == null)return list;
        Stack<Integer> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null){

        }


        return list;
    }


    /*不太理解*/
    public int maxDepth(TreeNode root) {
        //从左右结点 找出
        if (root == null){
            return 0;
        }else{
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return Math.max(left,right)+1;
        }
    }


    //层序遍历二叉树
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        if (root != null){
            queue.offer(root);
        }
        while(!queue.isEmpty()){
            //此层有多少个节点
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            //一次遍历此层的结点  并保存此层结点的下一个结点
            for (int i = 0; i < size; i++) {
                TreeNode curNode = queue.poll();
                list.add(curNode.val);
                //保存下一节点
                if (curNode.left != null){
                    queue.offer(curNode.left);
                }
                if(curNode.right != null){
                    queue.offer(curNode.right);
                }
            }
            result.add(list);
        }
        return result;
    }

    //判断是否为对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null)return false;

        return true;
    }

    //翻转二叉树 并返回根节点
    public TreeNode invertTree(TreeNode root) {

        return root;
    }

    //路径总和从根节点到叶子结点的路径总和 root为根节点  targetSum为目标路径总和
    public boolean hasPathSum(TreeNode root, int targetSum) {
        int sum = 0;
        //深度优先搜索法


        return false;
    }




















}
